Display Generated by a Generalized Cone Representation

Eiichi  Miyamoto:  Department of  Information  Engineering,  Hokkaido
University, Sapporo, Japan.

Thomas  O.   Binford:  Artificial  Intelligence  Laboratory, Stanford
University, Stanford, Calif, 94305.
                                  Abstract

We  describe  the  generalized  cone  representation  and   its  data
structure  for  a  class  of three-dimensional  curved  objects,  and
describe  an  algorithm for  hidden  line elimination  for displaying
objects.   In  the  generalized  cone representation,  an  object  is
represented by a  sequence of disjoint slices called  cross sections,
normal  to a space curve called the spine.   Accordingly,   an object
is   displayed with   cross section   edges and   longitudinal  edges
which  connect  corresponding points of two adjacent  cross sections.
Modelling by generalized cones simplifies input for curved objects.

 The program  first  suppresses hidden lines  within  a segment  of a
part, between  two adjacent  cross sections.   Lines hidden  by other
segments of parts are eliminated  by a brute force comparison  of one
segment versus every other segment.
                                    Introduction

We   require   that   a   representation   give   simple   part/whole
decompositions for familiar objects,  decompositions which correspond
to   our intuitive   sense of   parts.   Like   most representations,
the Generalized  Cone representation   is a  part/whole  graph  of an
object structured  into parts  by  cutting  and pasting.   The  parts
may  be structured  into  subparts  to  any  depth.    The difference
between  representations  is   the  choice   of  primitives  and  the
process   which  generates   descriptions  of   objects  within   the
representation.   The design criteria for generalized cone primitives
are:  a) parts   should  be defined  by continuity;  b)  parts should
correspond  to our  intuitive notion   of parts;  c)  parts  which we
regard as similar  should have a simple sense  of similarity   in the
representation; d)  relationships which we regard  as significant for
shape description,  such as thin, should be explicit.  These criteria
imply that primitives should  be volumes rather than  surfaces.  Most
people regard a  block as a single  part, rather than as  six surface
parts.   That  is,   we  don't  segment  at   surface  discontinuity.
Further,  parts  should   be  generated   by  local   volumes;    our
intuitive  segmentations   require  a   rich  set  of primitives.  We
want the local  volumes to be  disjoint for our  own  convenience  in
visualizing.     Thus,  we   seek   volume   primitives   defined  by
continuity.  Generalized cone primitives are defined by a sequence of



thin  slices  normal to  some  space curve   called  the  spine.  The
slices can  be described  by a  continuous function (whose value is a
cross section) along   the  spine.    The  representation   is  based
on  the "generalized  translational invariance"  formalism.   In this
formalism, normal cross sections  are mapped into other  normal cross
sections by translation  followed by some  congruence transformation.
For example,  a cylinder  is defined by  any plane  figure translated
along a straight  line.   A  cone is   defined by  any  plane  figure
translated  along a straight  line,  with a  scaling  function  which
is  linear along  the line.

The representation  of  cross sections  is the  same  problem in  two
dimensions.   The  representation of cross  sections is  a part/whole
representation, with area primitives (not curve primitives) connected
by cutting and pasting.  The primitives are formalized by generalized
translational  invariance in two dimensions, expressed  in terms of a
plane curve called the spine, and straight lines normal  to the spine
(cross sections of one-dimension).

The representation  has been used  in scene analysis  for description
and  recognition   of   curved   objects  [Nevatia,   Agin].      The
representation  describes  parts with  cross  sections  which  change
smoothly along some space curve.
          Data Structure for Generalized Cone Representation

In  the  program,  parts are  described  as  interpolation  functions
(splines)  for samples of cross  sections normal to the  spine.  Thus
parts are  represented as  sequences of  cross sections.   The  cross
sections are described in curve  form, as interpolation functions for
curve samples.  Cross sections may be circles or combinations of line
segments and  arcs.   That  representation for  cross sections  is an
expedient;  it  is inconsistent  with  the  representation for  cross
sections   described  above.     There  are   cross   section   edges
and longitudinal  edges  which  tie  together   corresponding  points
of  adjacent  cross   sections.  Although  arcs   or  curves  are now
displayed  as  line  segments,  the  display  of  longitudinal  edges
connecting  points  on  arcs may  be  suppressed,  because  these are
artifacts.

Each sample  point along a  cross section  is specified by  Cartesian
coordinates  in  the sense  of  a  right screw  in  the  direction of
generation of  the object  (in the  order of  cross  section).   This
ordering determines the interior of the object.  Each point lies on a
cross section edge and a longitudinal edge.  Each edge may be divided
into an arbitrary number of segments by hidden line elimination.

Each object has its own  coordinate system and a relationship  to the



coordinate system of a parent  object or of the world.  Objects which
have the  same parent  are  called siblings.    There exists  a  tree
structure among objects.

When  objects  are   displayed,  their  local  coordinates   must  be
transformed  into  world coordinates.    Let T   be   the translation
                                              i
vector and let R  be  the rotation matrix for transformation  of  the
                i
 t
i h child  to world coordinates.   Then we can set  up  the following
relations:
    T  = T   + R   t     ,
     i    i-1   i-1 i-1,i
    R  = R   r     ,
     i    i-1 i-1,i

where T   is the zero vector and  where R  is the unit matrix.  Here,
       0                                 0
                                   T
t        =   (x     ,y     ,z     )     is   the  translation  vector
 i-1,i         i-1,i  i-1,i  i-1,i
           th
from  the i    child  coordinate frame  to its parent's frame, and
                        i   j   k
                         x   x   x
        r      =     i   j   k
         i-1,i        y   y   y
                        i   j   k
                         z   z   z

                                                          th
is the rotation matrix from the coordinate  frame of the i   child to
its  parent's frame.   The rotation  can  be specified by  a rotation
vector for which the  direction of the  vector specifies the axis  of
rotation  and the  magnitude of  the  vector specifies  the angle  of
rotation in radians.   Given such a rotation  vector w , w ,  w  with
                                                      x   y    z
direction cosines c , c , c  and magnitude W in  radians.  Let  c  be
                   x   y   z                                     w
cos(W)  and  s  be  sin(W).   Then the  relation  between  a rotation
              w
matrix and a rotation vector is as follows:
        i  = (1-c )c c  + c
         x       w  x y    w
        j  = (1-c )c c  + c s
         x       w  x y    z w



        k  = (1-c )c c  + c s
         x       w  x z    y w
        i  = (1-c )c c  + c s
         y       w  y x    z w
        j  = (1-c )c c  + c
         y       w  y y    w
        k  = (1-c )c c  - c s
         y       w  y z    x w
        i  = (1-c )c c  - c s
         z       w  z x    y w
        j  = (1-c )c c  + c s
         z       w  z y    x w
        k  = (1-c )c c  + c
         z       w  z z    w

The screen is chosen as the plane z =  0, and the observer is located
at  the point (0,0,c), in  the world coordinates, where  c>0.  Then a
point  (x,y,z)   in   world  coordinates   projects  to   the   point
(cx/(c-x),cy/(c-y)) on the screen.
                       Hidden Line Elimination

Let us define a piece as the volume between  a pair of adjacent cross
sections.  First,  lines within a piece are eliminated as follows.  A
surface is  visible  if the  normal to  the  surface has  a  positive
component  along the  ray to  the observer.   An  edge is  visible if
either  surface is   visible  at the   edge.   Because of   the sense
of ordering of cross sections, the first cross section is  visible if
its edges  have a clockwise   sense on  the screen,  and  the  second
cross section is visible  if its edges have a  counterclockwise sense
on  the screen.   If the cross section  is convex, the  angle between
successive edges   will be  less than  pi  for clockwise  image,  and
greaer  than pi  for   counterclockwise image.     However,   if  the
cross  section  is nonconvex,  the sum  of angles  between successive
edges will  be 2π if clockwise and -2π if negative.

A  longitudinal plane is  visible if  the angle from  a cross section
edge of  the first  cross section  to  the longitudinal  edge in  the
counterclockwise   sense   is   less  than   π.    (Figure   2).   At
concavities in cross   sections, invisible  longitudinal   planes may
hide  planes  visible by   the  above  condition  (figure  1a).  That
portion  of   the  partially  visible   plane   which   overlaps  the
invisible  plane  is obscured.

The contour edges  of a piece are  those with one visible  surface at
the  edge.    At  concavities  in  the  cross  section,  portions  of
longitudinal edges are interior to  the contour of the piece  (figure
1a).



To eliminate edges  obscured by other pieces, each  piece is compared
with  every  other  piece.    Bounding  rectangles  aligned with  the
coordinate axes of the screen are calculated, and  those pieces whose
bounding rectangles  are disjoint are  immediately ignored.   For the
rest, for  each edge  on  the contour  of a  piece,  if there  is  an
apparent intersection with  edges of the  contour of the  other piece
(within  the line intervals), it  is determined which  line is nearer
the observer at the apparent intersection.

In cases in which the projection of an object is entirely  within the
projection of another object, there is no intersection.  To determine
this  case, the  apparent intersections  of an  extended edge  of the
contour of one piece with  the contour of the other piece  are found.
If  two intersections are  found on  different sides  of the  line, a
hypothetical line is considered between the two intersections for the
larger piece, and it is decided which edge is nearer.  This fails for
some   nonconvex  pieces.     If  the   projections  of   the  pieces
are disjoint,  the two  intersections fall  on the  same side  of the
line.

After the decision of  which piece is  closer, every visible line  of
the further  piece is  checked to remove  the hidden  portion between
apparent  crossing points with  the contour of  the  occluding piece.
Figure 5 demonstrates complex objects after execution  of hidden line
elimination.
                                 Conclusion

The representation of an  object by disjoint slices is convenient for
use in  vision and  planning for  manipulation.   In this  case,  the
primary advantages are ease of input, display  of curved objects with
no artifact edges,  and compact data structure.  The program is being
extended  to   adequately  deal   with  hollow   objects  and   other
nonconvexities.

Reference:  1) Bruce  G. Baumgart;  "Geometric Modeling  for Computer
Vision";  Stanford Artificial Intelligence  Laboratory, Memo AIM-249,
Stanford University, October 1974.